//Sunday, November 29 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

const int INF = 1000000000;
int cache[51];
string sentence;
vector <string> validWords;
class SentenceDecomposition
{
public:
	int decompose(string sen, vector <string> valid)
	{
		sentence = sen;
		validWords = valid;
		memset(cache, -1, sizeof(cache));
		int ret = cal(sentence.size());
		if(ret == INF) ret = -1;
		return ret;
	}
	int cal(int length)
	{
		int &ret = cache[length];
		if(ret != -1) return ret;
		ret = INF;
		if(length == 0) ret = 0;
		for(int i=0; i<validWords.size(); i++)
		{
			int len = validWords[i].size();
			if(len > length) continue;
			int v = cost(sentence.substr(length - len, len), validWords[i]);
			if(v == -1) continue;
			ret = min(ret, v+cal(length-len));
		}
		return ret;
	}
	int cost(string A, string B)
	{
		if(A.size() != B.size()) return -1;
		string str1 = A;
		string str2 = B;
		sort(str1.begin(), str1.end());
		sort(str2.begin(), str2.end());
		if(str1 != str2) return -1;
		int ret = 0;
		for(int i=0; i<A.size(); i++)
			if(A[i] != B[i])
				ret++;
		return ret;
	}
};
